package sort;

import java.util.Arrays;

public class QuickSort implements MySort {
    public static void main(String[] args) {
        int a[] = {8,9,1,7,2,2,5,4,6,0};
        //int a[] = {5,4};
        QuickSort quickSort = new QuickSort();
        quickSort.sort(a);
        System.out.println(Arrays.toString(a));
    }
    @Override
    public void sort(int[] a) {
        sortStep(a,0,a.length-1);
    }

    public void sortStep(int[] a,int start,int end){
        if(end-start<1){
            return;
        }

        int temp;
        int i=start;
        int j=end;
        int kiv = a[(start+end)/2];
        //i和j不用于遍历数组移动元素，ij最终的位置也是两个子数组的start2和end1
        while(i<j){
            while(i<=end&&a[i]<kiv){
                i++;
            }
            while(j>=start&&a[j]>kiv){
                j--;
            }
            if(i>=j){
                break;
            }

            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            //如果不加下面代码，kiv有重复值时就会死循环
            if (a[i]==kiv){
                j--;
            }
            if(a[j]==kiv){
                i++;
            }
        }

        //i和j不一定相等，i和j相等表示都指向了数组的中轴，需要对其偏移，i和j如果不相等说明二者是子数组的start和end
        if(i==j){
            i=i+1;
            j=j-1;
        }

        System.out.println(Arrays.toString(a));
        sortStep(a,start,j);
        sortStep(a,i,end);
    }
}
